from typing import List


class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        results = []
        if n==0:
            return results
        inputs_list = ["(", ")"]
        def dfs(string:str,):
            if len(string)==2*n:
                results.append(string)
                return
            
            for it in inputs_list:
                dfs(string+it)
        dfs("")
        ans = []
        for i in results:
            if self.isValid(i):
                ans.append(i)
        return ans


    def isValid(self, s: str) -> bool:
        stack1 = []
        input_str =  ["(", "[", "{"]
        map = {")":"(", "]":"[", "}":"{"}

        for c in s:
            if c in input_str:
                stack1.append(c)
            else:
                if len(stack1)==0:
                    return False
                if map[c] == stack1[-1]:
                    stack1.pop()
                else:
                    return False
        return len(stack1)==0
    
    def generateParenthesis1(self, n: int) -> List[str]:
        res = []
        def backtrack(in_idx, out_idx, tmp_res):
            if in_idx>n or out_idx>n:
                return 
            
            if len(tmp_res)==2*n:
                res.append(tmp_res)
                return
            
            if in_idx<n:
                backtrack(in_idx+1, out_idx, tmp_res+"(")
            if in_idx > out_idx:
                backtrack(in_idx, out_idx+1, tmp_res+")")
        backtrack(0,0,"")
        return res



